#include "hpoly.h"
#include "test.h"
#include "stdio.h"

static void TestConstruct()
{
   HPoly p;
   CHECK_EQ(p.p_str(), "0");

   p = "x^2+x";
   CHECK_EQ(p.p_str(), "x^2+x");

   p = "x^200+x^200+x^100+x+1";
   CHECK_EQ(p.p_str(), "x^100+x+1");

   p = "x^200+2x^200+3x^100+x+1";
   CHECK_EQ(p.p_str(), "x^200+x^100+x+1");

   p = "5x^100+3x^200";
   CHECK_EQ(p.p_str(), "x^200+x^100");

   p = "6x^200+4x^100+2x+2";
   CHECK_EQ(p.p_str(), "0");

   p = "6x^200+4x^100+2x+3";
   CHECK_EQ(p.p_str(), "1");

   p = "6x^200+4+4x^100+2x+3+5";
   CHECK_EQ(p.p_str(), "0");

   p = "6x^200+4x^100+21x+123";
   CHECK_EQ(p.p_str(), "x+1");
}

static void TestPlus()
{
   HPoly p1, p2, p;
   p1 = "x^200+x^100+x+1";
   p2 = "x^150+x^120+x+1";
   p = p1 + p2;
   CHECK_EQ(p.p_str(), "x^200+x^150+x^120+x^100");

   p1 = "x^200+x^100+x+1";
   p2 = "x^200+x^100+x+1";
   p = p1 + p2;
   CHECK_EQ(p.p_str(), "0");
}

static void TestMul()
{
   HPoly p1, p2, p;
   p1 = "x^2+1";
   p2 = "x^3+x";
   p = p1 * p2;
   CHECK_EQ(p.p_str(), "x^5+x");
   p1 = "x^4+x^2+1";
   p2 = "x^4+x^2+1";
   p = p1 * p2;
   CHECK_EQ(p.p_str(), "x^8+x^4+1");
   p1 = "x^4+x^2+1";
   p2 = "x^5+x^3+x";
   p = p1 * p2;
   CHECK_EQ(p.p_str(), "x^9+x^5+x");
}

static void TestDiv()
{
   HPoly p1, p2, p;
   p1 = "x^5+x";
   p2 = "x^3+x";
   p = p1 / p2;
   CHECK_EQ(p.p_str(), "x^2+1");
   p1 = "x^8+x^4+1";
   p2 = "x^4+x^2+1";
   p = p1 / p2;
   CHECK_EQ(p.p_str(), "x^4+x^2+1");
   p1 = "x^18+x^14+x^2+x^4+1";
   p2 = "x^4+x^2+1";
   p = p1 / p2;
   CHECK_EQ(p.p_str(), "x^14+x^12+x^10+x^6+x^4");
   p1 = "x^20+x^17+x^9+x^3+x";
   p2 = "x^8+x^3";
   p = p1 / p2;
   CHECK_EQ(p.p_str(), "x^12+x^9+x^7+x^4+x^2+x");
}

static void TestMod()
{
   HPoly p1, p2, p;
   p1 = "x^5+x";
   p2 = "x^3+x";
   p = p1 % p2;
   CHECK_EQ(p.p_str(), "0");
   p1 = "x^8+x^4+1";
   p2 = "x^4+x^2+1";
   p = p1 % p2;
   CHECK_EQ(p.p_str(), "0");
   p1 = "x^18+x^14+x^2+x^4+1";
   p2 = "x^4+x^2+1";
   p = p1 % p2;
   CHECK_EQ(p.p_str(), "x^2+1");
   p1 = "x^20+x^17+x^9+x^3+x";
   p2 = "x^8+x^3";
   p = p1 % p2;
   CHECK_EQ(p.p_str(), "x^7+x^5+x^4+x^3+x");
}

static void TestMulMod()
{
   HPoly p1, p2;
   p1 = HPoly("x^3+x") * HPoly("x^2+1");
   p1 = p1 % HPoly("x^3+x");
   CHECK_EQ(p1.p_str(), "0");
   p2 = HPoly("x^3+x").mulBase("x^3+x", "x^2+1");
   CHECK_EQ(p1.p_str(), p2.p_str());

   p1 = HPoly("x^5+x^3+x") * HPoly("x^3+x^2+1");
   p1 = p1 % HPoly("x^4+x");
   CHECK_EQ(p1.p_str(), "x^3+x^2+x");
   p2 = HPoly("x^4+x").mulBase("x^5+x^3+x", "x^3+x^2+1");
   CHECK_EQ(p1.p_str(), p2.p_str());

   p1 = HPoly("x^9+x^5+x^3+x") * HPoly("x^6+x^3+x^2+1");
   p1 = p1 % HPoly("x^4+x^2+x");
   CHECK_EQ(p1.p_str(), "x^2+x");
   p2 = HPoly("x^4+x^2+x").mulBase("x^9+x^5+x^3+x", "x^6+x^3+x^2+1");
   CHECK_EQ(p1.p_str(), p2.p_str());

   p1 = HPoly("x^14+x^9+x^5+x^3+x") * HPoly("x^13+x^6+x^3+x^2+1");
   p1 = p1 % HPoly("x^4+x+1");
   CHECK_EQ(p1.p_str(), "x^3");
   p2 = HPoly("x^4+x+1").mulBase("x^14+x^9+x^5+x^3+x", "x^13+x^6+x^3+x^2+1");
   CHECK_EQ(p1.p_str(), p2.p_str());
}

static void TestPowMod()
{
   HPoly p1, p2;
   p1 = HPoly("x^2+1") * HPoly("x^2+1");
   p1 = p1 % HPoly("x^3+x");
   p2 = HPoly("x^3+x").powBase("x^2+1", 2ul);
   CHECK_EQ(p1.p_str(), p2.p_str());

   p1 = HPoly("x^5+x^3+x") * HPoly("x^5+x^3+x");
   p1 = p1 % HPoly("x^4+x");
   p2 = HPoly("x^4+x").powBase("x^5+x^3+x", 2ul);
   CHECK_EQ(p1.p_str(), p2.p_str());

   p1 = HPoly("x^9+x^5+x^3+x") * HPoly("x^9+x^5+x^3+x");
   p1 = p1 * p1;
   p1 = p1 % HPoly("x^4+x^2+x");
   p2 = HPoly("x^4+x^2+x").powBase("x^9+x^5+x^3+x", 4ul);
   CHECK_EQ(p1.p_str(), p2.p_str());
}

static void TestGCD()
{
   CHECK_EQ(polyGCD(HPoly("x^3+x"), HPoly("x^3")).p_str(), "x");
   CHECK_EQ(polyGCD(HPoly("x^7+x^2+1"), HPoly("x^3+x+1")).p_str(), "1");
   CHECK_EQ(polyGCD(HPoly("x^5+x^4+x^2+x"), HPoly("x^6+x^5+x^4+x^3+1")).p_str(), "x^2+x+1");
}

static void TestIrr()
{
   CHECK_TRUE(!polyIrr(HPoly("x^5+x^1+1")));
   CHECK_TRUE(polyIrr(HPoly("x^5+x^2+1")));
   CHECK_TRUE(polyIrr(HPoly("x^5+x^3+1")));
   CHECK_TRUE(!polyIrr(HPoly("x^5+x^4+1")));

   CHECK_TRUE(polyIrr(HPoly("x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x+1")));
   CHECK_TRUE(!polyIrr(HPoly("x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^4+x+1")));

   HPoly p = "x^89+1";
   for (int i=1; i<89; i++)
   {
      p.toInteger().setBit(i);
      if ((i==38)||(i==51))
         CHECK_TRUE(polyIrr(p))
      else
         CHECK_TRUE(!polyIrr(p))
      p.toInteger().clrBit(i);
   }

   p = HPoly("x^3+x+1") + HPoly("x^3+x");
   p = p * HPoly("x^4");
   p = p % HPoly("x^4+x+1");
   CHECK_EQ(p.p_str(), "x+1");

   p = HPoly("x^5") + ((HPoly("x^6") * HPoly("x^4"))/(HPoly("x^12")%HPoly("x^4+x+1")));
   p = p % HPoly("x^4+x+1");
   CHECK_EQ(p.p_str(), "x^3+x^2+1");
}

static void TestPrime()
{
   CHECK_TRUE(polyIrr(HPoly("x^16+x^6+x^2+x+1")));
   CHECK_TRUE(!polyPrime(HPoly("x^16+x^6+x^2+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^11+x^2+x+1")));
   CHECK_TRUE(!polyPrime(HPoly("x^16+x^11+x^2+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^5+x^3+x+1")));
   CHECK_TRUE(!polyPrime(HPoly("x^16+x^5+x^3+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^10+x^3+x+1")));
   CHECK_TRUE(!polyPrime(HPoly("x^16+x^10+x^3+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^11+x^3+x+1")));
   CHECK_TRUE(!polyPrime(HPoly("x^16+x^11+x^3+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^12+x^3+x+1")));
   CHECK_TRUE(polyPrime(HPoly("x^16+x^12+x^3+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^6+x^4+x+1")));
   CHECK_TRUE(polyPrime(HPoly("x^16+x^6+x^4+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^15+x^4+x+1")));
   CHECK_TRUE(polyPrime(HPoly("x^16+x^15+x^4+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^12+x^6+x+1")));
   CHECK_TRUE(polyPrime(HPoly("x^16+x^12+x^6+x+1")));

   CHECK_TRUE(polyIrr(HPoly("x^16+x^10+x^7+x+1")));
   CHECK_TRUE(polyPrime(HPoly("x^16+x^10+x^7+x+1")));
}

void TestPoly()
{
   TestConstruct();
   TestPlus();
   TestMul();
   TestDiv();
   TestMod();
   TestMulMod();
   TestPowMod();
   TestGCD();
   TestIrr();
   TestPrime();
}
